#include <stdio.h>
#include <stdlib.h>

//选择排序
/*
1、简单选择排序
每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

不稳定


2、堆排序

堆：
若n个关键字序列L[1...n]满足下面某一条性质， 则称为堆(Heap) :
①若满足: L(i) ≥ L(2i)且 L(i) ≥ L(2i+1) (1 ≤ i ≤ n/2) ————大根堆(大顶堆)  在完全二叉树中，根≥左、右
②若满足: L(i) ≤ L(2i)且 L(i) ≤ L(2i+1) (1 ≤ i ≤ n/2) ————小根堆(小顶堆)  在完全二叉树中，根≤左、右


如何建立大根堆：
思路：把所有终端结点都检查一遍，是否满足大根堆的需求，如果不满足，则进行调整，将当前结点与更大的孩子互换
从非终端结点的最后一个开始，如果某一个互换破坏了下一级的堆，则继续调整
在顺序存储的二叉树中，非终端结点编号 i ≤ n/2 向下取整

堆排序：
每一趟将推顶元素加入有序子序列（与待堆排序序列中的最后一个元素互换）,
并将待堆排序元素序列再次调整为大根堆


总结：
1、不稳定
2、时间复杂度： 建堆 O(n)  排序 O(nlog n)


堆的插入和删除（小根堆为例）
插入：
对于小根堆，新元素放到表尾，与父节点对比,
若新元素比父节点更小，则将二者互换。新元素
就这样一路“上升”，直到无法继续上升为止

删除：
被删除的元素用堆底元素替代，然后让该
元素不断“下坠”，直到无法下坠为止




*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}